Internet Info 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / ien / ien-147 < prev next >

Wrap

Text File | 1988-12-01 | 17.0 KB | 474 lines

UTILIZING INTERNET ROUTES AS EXPRESSWAYS THROUGH SLOW NETS IEN #147 PRTN #290 Radia Perlman June 1980 INTRODUCTION Some networks in the catenet are very slow relative to others. An example is a very large packet radio network, which might be 100 PR hops from end to end. Distributed throughout the slow net might be several gateways to a faster net. It would be desirable to utilize the internet to quickly route packets through the slow net. So in the particular example, rather than delivering a packet through 100 PR hops, it would be desirable to deliver the packet to the nearest gateway in the PR net, and have that gateway deliver the packet, through the internet, to a gateway close to the destination of the packet. This problem was presented by Dr. Vinton Cerf at the May 1980 Internet meeting. This paper is an approach to solving the problem on a specific case basis, and an argument for solving it that way rather than as a generalized internet routing problem. WHY IT IS NOT THE CATENET'S JOB The catenet is a network of nets. Its job is to deliver a packet as efficiently as possible to the correct net. It should not have to worry about the internal structure of a network to the extent of knowing which hosts are closest to which gateways. It is reasonable for the catenet to know enough about nets to take into account their properties when calculating internet routes. For instance, according to whatever cost function gateways are using to calculate catenet distances, one net can be many times the cost of another. And if gateways wished to calculate distances to their neighbor gateways, and if there were three gateways G1, G2, and G3 on a net N, the link G1-G2 could have a different cost from the link G1-G3. However, the catenet should route to destination networks based solely on the most efficient internet route to that network, and let the destination network handle delivery to the host on the network as it sees fit. - 1 - HOW A SPECIFIC NETWORK CAN USE A NEARBY FAST NET The previous section does not imply that the internet cannot be utilized as an express route through a slow net. What it says is that it is the job of a local net, rather than the catenet, to utilize the capability. And it is not difficult to design this into a net. net S I net F ________________________________________ I I I A I I . I I ...N1--G1S-G1-G1F.. I I . I I . I I . I I . I .N2--G2S-G2-G2F.. I . I I . I I .B I I I ________________________________________ We are assuming a slow net with a few gateways to a faster network. Call the slow net S, and the fast net F. Assume two gateways, both on both S and F. The addresses of the first gateway are G1S and G1F, with G1S being G1's local address on net S. The addresses of the second gateway are G2S and G2F. Assume G1S is connected to node N1 on net S, and G2S is connected to node N2 on S. (I am assuming a network like the ARPANET or the PRnet, in which hosts are not nodes on the net, but are attached to nodes on the net.) Node A on net S wishes to communicate with node B on net S. A and B are distant in net S, and A is close to G1, and B is close to G2. A can communicate with B via A's route to G1, G1's route through net F to G2, and G2's route to B in S by prepending to the packet an internet header with a one level source route, and sending the packet to gateway G1. The one level source route is the address on the fast net of the destination gateway, i.e., <net F, host G2F>. The destination in the internet header is the internet address of the destination of the packet, i.e., <net S, B>. When G1S receives the packet, it will route it to internet address F,G2F. Since that internet address is on net F, G1 will route the packet through net F to G2. When G2 receives the packet, it will advance the source route and forward the packet to internet address <S,B>. So the packet travels A=>G1 through S, G1=>G2 through F, and finally G2=>B through S, as desired. - 2 - The source route is essential because if G1 is given a packet with an internet address on net S, it will just throw the packet back into net S directly, because no matter how cheap its link to G2 is through net F, it cannot be cheaper than 0, which is G1's distance to net S, because G1 is directly connected to S. In most network designs, you would want most of net S to be unburdened with knowledge of the internet, neighboring fast net, internet headers, etc. Thus a reasonable design is that nodes on S have some local net link-link protocol, and some routing information about links that gets passed around. The nodes directly attached to the gateways, N1 and N2, utilize the foreign net as a "link" between themselves. To do this, they must encapsulate local net packets for transmission across this "link", within internet packets, since the "link" is actually the internet. N1 adds an internet header to the packet with a one-level source route being the internet address of the second gateway on the fast net, and internet destination address <S,N2>, and passes the packet off to the gateway. N2 strips off the internet header and continues the packet along the local net route. The rest of the nodes on S can be ignorant of just what mechanism is employed when N1 and N2 communicate. All they know is that N1 and N2 report that they can get packets to each other with some miraculously low cost. They believe N1 and N2, and find when they compute routes that many local routes will take advantage of that high speed link. N1 and N2 do not have to know very much about net F. For N1 to send a packet to N2, all it needs to do is send its attached gateway the packet with a prepended internet header with single-level source route <F,G2> and destination internet address <S,N2>. N2 must be able to strip off the added internet header and continue the packet in the local net as if the N1-N2 link were an ordinary link in that net. (In IEN #140, "Mutual Encapsulation of Internetwork Protocols", the authors give another example of using one net as if it were a link in another net -- the encapsulation of PUPs in IP datagrams.) There are some nets in which only hosts are addressable, not nodes ("imps"). It is important, however, as discussed above, to have N1 be able to put N2 as the internet destination. If N1 merely put B (the destination host) as the internet destination, N2 would not know to strip off the internet header. Packets should not arrive looking different depending on what path they take, so it is at least ineligent to have some packets arriving at B with internet headers. Worse yet, B might not know about internet headers -- it might be a host that only communicates with other entities on the local net. And another problem is that if the route through the net traversed several express hops, several internet headers would be prepended, one after another, onto the packet. So the answer to this problem is that N1 must be able to have as the internet address N2. The code in N2 to strip off internet addresses can be thought of as a virtual host - 3 - attached to N2, so there should be no problem assigning it an internet address. THE MULTISTATION PACKET RADIO NET For those of you uninterested in the packet radio net, skip this section. Briefly, the packet radio network consists of nodes called PRs, each of which has a unique ID. Hosts, terminals, etc., are known as devices, and can be attached to any PR, and unplugged from a PR and moved to another PR without impact since device/PR correspondence is dynamically bound by the network. Devices also each have a unique ID. Routing is calculated by special devices known as stations. A route consists of a sequence of IDs, currently all of which would be PR IDs. Presumably each PR in the route is in direct radio connectivity of the next PR along the route. In the current design, station-station links are assumed to be ordinary packet radio multihop routes. Suppose that some of the stations were directly connected to each other with some sort of high speed, high bandwidth lines. The only modifications necessary to the design of the net to utilize these lines are that: 1) a station ID can appear in a route 2) a PR checks to see if the next ID in the route is its directly attached station. If so, rather than broadcasting the packet, it sends the packet to its attached station. 3) a station attached to other station(s) via high speed lines must be able to handle a packet by looking to see the next ID in the route and handing the packet to the correct next station, or to its attached PR (if the next ID was the station's attached PR) 4) stations would take these high speed lines into account in calculating routing in their subnets, and in calculating their distance to their neighbor stations in the station-net. Suppose instead that there are gateways (which are devices) to a faster net interspersed throughout the PRnet. Assume the gateways are not in stations. The modifications necessary to the PRnet design to utilize them are: 1) a device ID must be able to appear in a route 2) a PR must check to see if the next ID in the route is its attached device. If so, the PR must prepend an internet header with single level source route being <net F (a constant assembled into the PR's program), host X> (where X is the next ID in the route (and if the internet local name doesn't fit into a PRnet unique ID, use two PRnet IDs, the - 4 - next 2 hops, to calculate what to put into X in the internet header)), and internet destination <PRnet (a constant assembled into the PR's program), ID of following hop of route>. 3) The PR receiving the packet from its attached device should strip off the internet header and continue the packet along the PRnet route. 4) Stations must know the gateway IDs so that they can recognize them as such when they are reported Suppose instead that the stations themselves are gateways, in that they are themselves connected to both nets. Then there is a choice of how to treat the design. It can either be treated as the standard gateway design just covered, or it can be treated as the slightly simpler case of direct lines between the stations, where the "direct lines" are actually routes through the fast net. In other words the stations can use the internet as their "direct link", or the fast net alone. COMPLICATIONS? In this section, I will present some variants of the basic problem, and show how they are not complications of the basic design. The first variant is when there are three nets, S (Slow), M (Medium), and F (Fast). There are a few gateways between S and M. There are a few gateways between M and F. There are no gateways between S and F. net F ...................... . . __________G____________________G______________ . . net M . . ..... ..... . . ______G____________________________G_________ . . ..... .. . . A B net S Routing in net M is exactly as described above. Net M can make use of the gateway links through net F. Routing in net S is also exactly as described above. Net S can make use of the gateway links through net M. S does not know anything about net F. It routes packets through net M, and is unaware that M cleverly makes use of net F. So a packet between two hosts A and B on S - 5 - might travel to a nearby S-M gateway, through M to an S-M gateway near B, and then to B. The path through M between the two S-M gateways might travel through net F for some part of the way. The important thing is that none of the nets needs to know exactly how the other net routes packets. The strange thing is that each time this happens a new internet header will be prepended to the packet. So in this example, while the packet is travelling through net F, there will be two levels of internet header on the packet. One might prefer instead to have a two-level source route on the packet. The reason I don't think that would be the right design is that it requires net M to understand that the packet travelling through its local net is an internet packet. I am assuming that while a packet is travelling through net M it has a local M-net header on it, and as far as net M is concerned, the internet header, which follows the local header, is just data. So entities on M would not be smart enough to strip off the local header and manipulate the internet header by adding more levels of source route. - 6 - I net I net F1 I F2 .............G.................. . I . . I . . I . ________G______________________________G_____________ . . ..... ... . . . . A B net S The next variant consists of three nets, S (Slow), F1 (fast net 1), and F2 (fast net 2). Assume a gateway between S and F1, a gateway between F1 and F2, and a gateway between F2 and S. Assume these are the only gateways, and the two gateways on S are distant from each other on S. Assume a host A on S close to the S-F1 gateway and a host B on S close to the S-F2 gateway. S should route packets between A and B through net F1, then net F2, and then to B. S handles this case exactly as all the others. The route through S goes first to a node attached to the S-F1 gateway, and that node prepends an internet header with the source route being the F2 address of the S-F2 gateway, and the internet destination being the S node attached to the S-F2 gateway, and gives the packet to the S-F1 gateway. The S-F1 gateway routes the packet as desired. So net S treats the S-F1 gateway as if it really were an S-F2 gateway in the original example. AN ALTERNATIVE TO SOURCE ROUTING FOR THIS CASE This design does not really utilize the general capabilities of source routing. Assuming source routing is implemented, it provides a convenient method of implementing the catenet as an express route through a slow net. However, it is probably cleaner to look at the solution in a slightly different way. With source routing, the packet header specifies a full internet address as an intermediate destination. In this case, the intermediate address is always a gateway. Assuming gateways were given unique IDs (as opposed to multiple internet addresses), it would be cleaner to specify a gateway ID rather than a <net, host ID> pair for a gateway. An example where it is cleaner is having three nets, S (slow), F1 (fast net #1), and F2 (fast net #2). Suppose two gateways, each connected to all three nets. When net - 7 - S wishes to utilize the catenet as an express route between the gateways, S does not care whether the catenet routes the packet over F1 or F2. But with source routing, S would have to specify one or the other. If instead S could merely give the unique gateway ID of the desired gateway, the catenet could choose over which path to send the packet to reach the other gateway. If the only utilization of source routing is to give a string of gateway addresses, perhaps source routing should be, instead of a string of internet addresses, a string of gateway IDs. In addition to possible cleanliness, this would save room in the header. CONCLUSIONS The catenet should be protected from knowledge of how local networks route packets. All the catenet should know is the cost of each gateway-gateway link, not the mechanism of packet travel on the link. Local networks should be mostly protected from knowledge of the internet. A network that was not originally designed as part of the catenet should be able to be connected to the catenet merely by adding a gateway to that net. The problem of utilizing faster neighbor nets can be solved in each net in which the opportunity exists in a not very costly or complicated manner, by adding sophistication only to the nodes directly connected to gateways. The rest of the local network can be oblivious of what is going on. - 8 - -------